package org.lscatbear.arithmetic.middle;

/**
 * @author EBU7-dev1-ayh
 * @create 2021/9/22 0022 17:01
 * 两数相加
 */


/**
 * <a hrf='https://leetcode-cn.com/problems/add-two-numbers/'>地址</a>
 * 给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
 * <p>
 * 请你将两个数相加，并以相同形式返回一个表示和的链表。
 * <p>
 * 你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
 * <p>
 *  
 * <p>
 * 示例 1：
 * <p>
 * <p>
 * 输入：l1 = [2,4,3], l2 = [5,6,4]
 * 输出：[7,0,8]
 * 解释：342 + 465 = 807.
 * 示例 2：
 * <p>
 * 输入：l1 = [0], l2 = [0]
 * 输出：[0]
 * 示例 3：
 * <p>
 * 输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
 * 输出：[8,9,9,9,0,0,0,1]
 *  
 * <p>
 * 提示：
 * <p>
 * 每个链表中的节点数在范围 [1, 100] 内
 * 0 <= Node.val <= 9
 * 题目数据保证列表表示的数字不含前导零
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/add-two-numbers
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class LeetCode02 {
	public static void main(String[] args) {
		ListNode l1 = new ListNode(2);
		l1.next = new ListNode(4);
		l1.next.next = new ListNode(3);
		ListNode l2 = new ListNode(5);
		l2.next = new ListNode(6);
		l2.next.next = new ListNode(4);
		System.out.println(fun02(l1,l2));
		System.out.println(init(new int[]{2,4,3}));
		System.out.println(initReverse(new int[]{2,4,3}));
	}

	public static ListNode init (int[] num){
		ListNode listNode = null;
		ListNode nextNode = null;
		for (int i = 0; i < num.length; i ++){
			if(listNode == null){
//				初始化头结点为第一个数，第二节点也第一个数
				listNode = nextNode = new ListNode(num[i]);
			}else{
//				如果已经存在，则将第二节点的下一个节点变为第二个数
				nextNode.next = new ListNode(num[i]);
//				将下一节点变为下一节点的下一节点
				nextNode = nextNode.next;
			}
		}
		return listNode;
	}

	public static ListNode initReverse (int[] num){
		ListNode listNode = null;
		ListNode nextNode = null;
		for (int i =  num.length - 1 ; i >= 0; i --){
			if(listNode == null){
//				初始化头结点为第一个数，第二节点也第一个数
				listNode = nextNode = new ListNode(num[i]);
			}else{
//				如果已经存在，则将第二节点的下一个节点变为第二个数
				nextNode.next = new ListNode(num[i]);
//				将下一节点变为下一节点的下一节点
				nextNode = nextNode.next;
			}
		}
		return listNode;
	}

	public static ListNode fun01(ListNode l1, ListNode l2){
		int carry = 0;
		ListNode sumList = null;
		ListNode sumNext = null;
		while (l1 != null || l2 != null){
//			如果l1不为空，则使用l1的值，否则使用0
			int n1 = l1 != null ? l1.val : 0;
			int n2 = l2 != null ? l2.val : 0;
//			求出两数之和并加上进位
			int sum = n1 + n2 + carry;
//			如果和链表为空，则需要进行初始化
			if(sumList == null){
//				初始化下一节点和和链表
				sumList = sumNext = new ListNode(sum % 10);
			}else{
//				和链表存在值，将下一位指定为当前和的十位数
				sumNext.next = new ListNode(sum % 10);
//				将下一位绑定到链表尾部
				sumNext = sumNext.next;
			}
//			求出进制的值
			carry = sum / 10;
//			重新赋值
			l1 = l1 != null ? l1.next : null;
			l2 = l2 != null ? l2.next : null;
		}
//		如果进制大于0，需要在链表尾进行添加
		if(carry > 0){
			sumNext.next = new ListNode(carry);
		}
		return sumList;
	}

	public static ListNode fun02(ListNode l1, ListNode l2){
		int carry = 0;
		ListNode pre = new ListNode(0);
		ListNode curr = pre;
		while (l1 != null || l2 != null){
			int n1 = l1 != null ? l1.val : 0;
			int n2 = l2 != null ? l2.val : 0;
			int sum = n1 + n2 + carry;
			carry = sum / 10;
			sum = sum % 10;
			curr.next = new ListNode(sum);
			curr = curr.next;
			l1 = l1 != null ? l1.next : null;
			l2 = l2 != null ? l2.next : null;
		}
		if(carry == 1){
			curr.next = new ListNode(carry);
		}
		return pre.next;
	}
}

class ListNode {
	int val;
	ListNode next;

	ListNode() {
	}

	ListNode(int val) {
		this.val = val;
	}

	ListNode(int val, ListNode next) {
		this.val = val;
		this.next = next;
	}

	@Override
	public String toString() {
		StringBuilder str = new StringBuilder("[");
		ListNode obj = this;
		while (obj != null){
			str.append(obj.val).append(",");
			obj = obj.next;
		}
		return str.substring(0, str.length() - 1) + "]";
	}
}
